import java.util.HashMap;

/**
 * @author zx
 * @date date 2019-12-01 22:15:17
 *
 * -------------滑动窗口-------------
 * 1.弄出匹配的dictT
 * 2.列出s,t的字母种类数目，方便匹配
 * 3.right指针右移进行大循环操作
 * 4.   取右指针指向的字母
 * 5.   碰到和字典单字母匹配时就formed++
 * 6.   左指针开始移动
 * 7.       记录下符合要求的一组，每次如果得到更短的就更新
 * 8.       左指针缩进
 * 9.       字母少于字典时更新formed--
 * --------------------------------
 */
public class T76 {
    private static String minWindow(String s, String t){
        int l = 0, r = 0;

        //windows length, left, right
        int ans[] = {-1, 0, 0};
        HashMap<Character, Integer> windowCount = new HashMap<Character, Integer>();
        HashMap<Character,Integer> dictT = new HashMap<Character, Integer>();


        //先弄出dictT
        for (int i = 0; i < t.length(); i++) {
            char ct = t.charAt(i);
            int countT = dictT.getOrDefault(ct, 0);
            dictT.put(ct, countT + 1);
        }

        //标志匹配到的字母的种类数
        int formed = 0;
        //需要匹配的字母种类数
        int required =dictT.size();

        while(r < s.length()){
            char cs_right = s.charAt(r);
            int countS = windowCount.getOrDefault(cs_right,0);
            windowCount.put(cs_right, countS + 1);

            if(dictT.containsKey(cs_right) && dictT.get(cs_right).equals(windowCount.get(cs_right))){
                formed++;
            }

            while (l <= r && formed == required){

                //记录下符合要求的一组，每次如果得到更短的就更新
                if (ans[0] == -1 || r - l + 1 <= ans[0]) {
                    ans[0] = r - l  + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                char cs_left = s.charAt(l);
                windowCount.put(cs_left, windowCount.get(cs_left) - 1);

                //别忘记更新formed
                if(dictT.containsKey(cs_left) && windowCount.get(cs_left) < dictT.get(cs_left)){
                    formed--;
                }
                l++;
            }

            r++;
        }

        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s,t));
    }
}
